package sorting

import "gitee.com/guuzaa/sorting/constraints"

func HeapSort[T constraints.Ordered](arr []T) []T {
	if len(arr) <= 1 {
		return arr
	}

	n := len(arr)
	lastParent := parent(n)
	for i := lastParent; i >= 0; i-- {
		moveDown(arr, i)
	}

	for end := n - 1; end >= 1; end-- {
		arr[0], arr[end] = arr[end], arr[0]
		moveDown(arr[:end], 0)
	}

	return arr
}

func moveDown[T constraints.Ordered](arr []T, parent int) {
	last := len(arr) - 1
	for {
		left, right := leftChild(parent), rightChild(parent)
		if left > last {
			break
		}

		child := left
		if right <= last && arr[left] < arr[right] {
			child = right
		}

		if arr[child] > arr[parent] {
			arr[child], arr[parent] = arr[parent], arr[child]
		}
		parent = child
	}
}

func parent(child int) int {
	return child / 2
}

func leftChild(parent int) int {
	return (parent * 2) + 1
}

func rightChild(parent int) int {
	return (parent + 1) * 2
}
